#include<iostream>

using namespace std;
int t,n,k,m;
int main(){
    cin>>t;
    while(t--){
        cin>>n>>k;
        for(int i=2;i<=n;i++){
            if(n%i==0){
                m=i;
                break;
            }
        }
        cout<<n+m+(k-1)*2<<endl;
    }

return 0;
}
